package algorithm.leetcode.medium;

/**
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/24
 */
public class Question93 {

    public static void main(String[] args) {

    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>(4);
        StringBuilder ip = new StringBuilder();
        int len = s.length();
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 4; j++) {
                for (int n = 1; n < 4; n++) {
                    for (int k = 1; k < 4; k++) {
                        if (i + j + n + k == len) {
                            int a = Integer.parseInt(s.substring(0, i));
                            int b = Integer.parseInt(s.substring(i, i + j));
                            int c = Integer.parseInt(s.substring(i + j, i + j + n));
                            int d = Integer.parseInt(s.substring(i + j + n));

                            if (a <= 255 && b <= 255 && c <= 255 && d <= 255) {
                                ip.append(a).append(".").append(b).append(".").append(c).append(".").append(d);
                                if (ip.length() == len + 3) {
                                    // 如果现在ip长度 == 字符串长度 + 3个"." 说明满足
                                    res.add(ip.toString());
                                }
                                // 清空进行下一论
                                ip.delete(0, ip.length());
                            }
                        }
                    }
                }
            }
        }
        return res;
    }

}
